package 校招笔试.华为校招;

import java.util.Arrays;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/3/3 19:14
 */
public class P1006数组取min {
    /*
     给定一个数组，可以给数组添加一个限制使得数组中的每一个数和限制取min， 如果 nums[i] <= min 取  nums[i],  反之 取 min
     要使数组的总和不超过 total，求限制最高可以取多少，
     如果不需要限制则返回-1。
       1 <= n , arr[i], total <= 10 ^ 5
     */

    /*
      暴力的 做法 就是 枚举 这个 limit 对吧
      二分答案 :
      这个题 还是 有很多的细节在里面!
     */
    public static  int solution(int nums[],int total){
        Arrays.sort(nums);
        int len = nums.length;

        int preSum [] = new int[len + 1];
        for(int i = 0;i < len;i++){
            preSum[i + 1] = preSum[i] + nums[i];
        }

        /*
         no need limit
         */
        if(preSum[len] <= total){
            return  -1;
        }

        //    limit 属于 [1, 10 ^ 5] ,直接二分分呗
        int l = 1, r = 100000; // or r = nums[len - 1]; 都行
        while(l < r){
            int mid = l + r + 1>> 1;
            if(check(mid,nums,preSum) > total){
                r = mid - 1;
            }
            else{
                l = mid;
            }
        }

        return l;
    }

    private static  int check(int aim, int[] nums,int preSum[]) {
            int l = 0, r = nums.length - 1;
            while(l < r){
                int mid = l + r + 1 >> 1;
                if(nums[mid] > aim){
                    r = mid - 1;
                }
                else{
                    l = mid;
                }
            }
            return preSum[l + 1] + (nums.length - l - 1) * aim;
    }

    public static void main(String[] args) {
        int total = 15,nums[] = {1,2,3,4,5};
        int solution = solution(nums, total);
        System.out.println(solution);
    }

}
